package com.cat.DataStructure04;

import java.math.BigInteger;
import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-numbers-with-non-decreasing-digits/
 * @create 2025/11/24 15:58
 * @since JDK17
 */

public class Solution04 {
    static int N = ((int) 1e9) + 7, MAXN = 501, b;
    static int[][]dp = new int[MAXN][11];
    int dfs(char[] num, int len, int pre, boolean isNum, boolean free) {
        if (len == num.length) {
            return isNum ? 1 : 0;
        }
        if (isNum && free && dp[len][pre] != -1) {
            return dp[len][pre];
        }
        int up = free ? b - 1 : num[len] - '0';
        long ans = 0;
        if (!isNum) {
            ans = dfs(num, len + 1, pre, false, true);
        }
        for (int i = isNum ? 0 : 1; i <= up; i++) {
            if (i >= pre) {
                ans = (ans + dfs(num, len + 1, i, true, free || i < up)) % N;
            }
        }
        if (isNum && free) {
            dp[len][pre] = (int)ans;
        }
        return (int)ans;
    }
    public int countNumbers(String l, String r, int b) {
        this.b = b;
        char[] low = new BigInteger(l).subtract(BigInteger.ONE).toString(b).toCharArray();
        char[] high = new BigInteger(r).toString(b).toCharArray();
        for (int i = 0; i < low.length; i++) {
            Arrays.fill(dp[i], -1);
        }
        int resL = dfs(low, 0, 0, false, false);
        for (int i = 0; i < high.length; i++) {
            Arrays.fill(dp[i], -1);
        }
        int resR = dfs(high, 0, 0, false, false);
        return (resR + N - resL) % N;
    }
}
